package it.storm.solution;

import java.util.Arrays;

/**
 * 1738. 找出第 K 大的异或坐标值
 * https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value/
 */
public class Solutions_1738 {
    public static void main(String[] args) {
//        int[][] matrix = {{5, 2}, {1, 6}};
//        int k = 1;  // output: 7

        int[][] matrix = {{5, 2}, {1, 6}};
        int k = 2;  // output: 5

//        int[][] matrix = {{5, 2}, {1, 6}};
//        int k = 3;  // output: 4

//        int[][] matrix = {{5, 2}, {1, 6}};
//        int k = 4;  // output: 0

        int result = kthLargestValue(matrix, k);
        System.out.println(result);
    }

    public static int kthLargestValue(int[][] matrix, int k) {
        if (matrix == null) {
            return 0;
        }
        // 在原数组上进行计算
        int row = matrix.length, col = matrix[0].length;
        int[] nums = new int[row * col];
        int idx = 0;
        nums[idx ++] = matrix[0][0];
        // 初始化第 1 行
        for (int i = 1; i < col; i++) {
            matrix[0][i] ^= matrix[0][i - 1];
            nums[idx ++] = matrix[0][i];
        }
        // 初始化第 1 列
        for (int i = 1; i < row; i++) {
            matrix[i][0] ^= matrix[i - 1][0];
            nums[idx ++] = matrix[i][0];
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                // 左边、上边，因为左边和上边都记录着左上区域的异或结果
                // 而左边和上边异或时，又将左上区域的异或结果抵消了，所以还需要异或上左上区域的结果
                matrix[i][j] = matrix[i][j] ^ matrix[i - 1][j]
                        ^ matrix[i][j - 1] ^ matrix[i - 1][j - 1];
                nums[idx ++] = matrix[i][j];
            }
        }
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}
